/*
The heap sort uses max heap, which is a complete binary tree.
The pseudo code can be found as follows:
max-heapify -> page 154
build-max-heap -> page 157
heap-sort -> page 160
*/

#include <iostream>
using namespace std;

int A[10]={4,1,3,2,16,9,10,14,8,7};
int heap_size = 10;
int leftIndex[10]={1,3,5,7,9,-1,-1,-1,-1,-1};  // index of left child
int rightIndex[10]={2,4,6,8,-1,-1,-1,-1,-1,-1}; // index of right child

void exchange(int *heap, int i, int j)
{
	// both i and j are the index of heap element
	int tmp = heap[i];
	heap[i] = heap[j];
	heap[j] = tmp;
	return;
}

void max_heapify(int *heap, int i)
{
	// Make one node and it's children as heapify
	// i is also the index of current element
	int left_index = leftIndex[i];
	int right_index = rightIndex[i];
	int largest_index;
		
	if((i>=0) && (i<heap_size) && (left_index<heap_size) && (heap[left_index] > heap[i])) // Must make sure the element swipped out cannot be swipped in
	{
		largest_index = left_index;
	}
	else
		largest_index = i;
	if((i>=0) && (i<heap_size) && (right_index<heap_size) && (heap[right_index] > heap[largest_index])) // Will compare the current largest and right.
	{
		largest_index = right_index;
	}
	if(largest_index != i)
	{	
		exchange(heap,largest_index,i);
		max_heapify(heap,largest_index);		
	}
}

void build_heap(int *heap)
{
	// Build the whole heap
	// The nodes with index > (heap_size/2) are leaf
	int i=heap_size/2;
	for(i=heap_size/2;i>-1;i--)
	{
		max_heapify(heap,i);
	}
}

void display()
{
	int i;
	for(i=0;i<10;i++)
		cout << A[i] << " ";
	cout << endl;
}

void heap_sort(int *heap)
{
	// First, build the heap
	build_heap(heap);
	// Extract the root of heap
	int i;
	for(i=heap_size-1;i>0;i--)
	{
		cout << heap[0] << endl;
		exchange(heap,0,i);
		display();
		heap_size--;
		max_heapify(heap,0);
		display();
	}
	cout << endl;
	 
}

int main()
{
	heap_sort(A);
}
